#ifndef _L_BV_TREE_120118_BV_TREE_ITER_H
#define _L_BV_TREE_120118_BV_TREE_ITER_H

#include <ltypes.h>
#include <lmacros.h>

#include <queue>

LLIB_BEGIN
namespace geom {

/* The abstract BVTree iterator class */
template <typename BVTree_t>
class BVTreeIter {
protected:
    /* The BVNode type */
    typedef typename BVTree_t::BVNode BVNode;

public:
    /* Here we define the traversal type for the factory method */
    enum TraversalType { Preorder = 0, Inorder = 1, Postorder = 2, Hierarchy = 3, LeafOnly = 4 };

    /* The factory method for build types of iterator on demand */
    static BVTreeIter<BVTree_t>* Create( BVTree_t& tree, TraversalType type);

    /* Restart the iterator from the beginning */
    inline void Restart() { reset(); }

    /* Get the next BVNode, return NULL when reach the end */
    virtual BVNode* Next() = 0;

protected:
    /* Hide default constructor */
    BVTreeIter() {}

    /* Reset internal states for a new traversal */
    virtual void reset() = 0;

    /* The BVTree pointer */
    BVTree_t* _tree;

};

/* The Preorder traversal BVTree iterator class */
template <typename BVTree_t>
class BVTreeIter_Preorder : public BVTreeIter<BVTree_t> {
public:
    virtual BVNode* Next();
protected:
    virtual void reset();
private:
    /* The preorder traversal helper stack */
    std::deque<BVNode*> _stack;
};

/* The Inorder traversal BVTree iterator class */
template <typename BVTree_t>
class BVTreeIter_Inorder : public BVTreeIter<BVTree_t> {
public:
    virtual BVNode* Next();
protected:
    virtual void reset();
private:
    /* The preorder traversal helper stack */
    std::deque<BVNode*> _stack;
};

/* The Postorder traversal BVTree iterator class */
template <typename BVTree_t>
class BVTreeIter_Postorder : public BVTreeIter<BVTree_t> {
public:
    virtual BVNode* Next();
protected:
    virtual void reset();
private:
    /* The preorder traversal helper stack */
    std::deque<BVNode*> _stack;
    BVNode* _lastPop;
};

} // end of namespace geom
LLIB_END

#include "BVTreeIter.hpp"

#endif
